#include <iostream>
#include "vector"
#include "map"
#include <unordered_map>
#include <stack>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <queue>
#include <cctype>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Codec
{
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {
        //通过二叉树创建string
        //其实是层序遍历
        //完全二叉树补齐
        if (root == NULL)
        {
            return "NULL";
        }
        string res;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty())
        {
            int size = que.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = que.front();
                que.pop();
                if (node == NULL)
                {
                    res += "null";
                }
                else
                {
                    res += to_string(node->val);
                    if (node->left)
                    {
                        que.push(node->left);
                    }
                    else
                        que.push(NULL);
                    if (node->right)
                    {
                        que.push(node->right);
                    }
                    else
                        que.push(NULL);
                }

                res += ",";
            }
        }
        class Codec
        {
        public:
            // Encodes a tree to a single string.
            string serialize(TreeNode *root)
            {
                //通过二叉树创建string
                //其实是层序遍历
                //完全二叉树补齐
                if (root == NULL)
                {
                    return "NULL";
                }
                string res;
                queue<TreeNode *> que;
                que.push(root);
                while (!que.empty())
                {
                    int size = que.size();
                    for (int i = 0; i < size; i++)
                    {
                        TreeNode *node = que.front();
                        que.pop();
                        if (node == NULL)
                        {
                            res += "null";
                        }
                        else
                        {
                            res += to_string(node->val);
                            if (node->left)
                            {
                                que.push(node->left);
                            }
                            else
                                que.push(NULL);
                            if (node->right)
                            {
                                que.push(node->right);
                            }
                            else
                                que.push(NULL);
                        }

                        res += ",";
                    }
                }
                res.pop_back();
                // string长度现在为奇数 没有最后一个逗号
                //需要去除最后多余的NULL
                for (int i = res.size(); i >= 0; i--)
                {
                    /* code */
                }

                cout << res;
                return res;
            }

            // Decodes your encoded data to tree.
            TreeNode *deserialize(string data)
            {
                return NULL;
            }
        };
        // string现在是
        cout << res;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {
        return NULL;
    }
};
int main()
{
    Solution s;
    vector<int> bills = {5, 5, 10, 10, 20};
    cout << s.lemonadeChange(bills);
    return 0;
}